package com.quickSort;

import com.Sort;
import com.insertSort.InsertionSort;

public class QuickSort<Item extends Comparable<Item>> extends Sort<Item> {

    private int M = 15;

    Sort<Item> insertionSort = new InsertionSort<Item>();

    @Override
    public void sort(Item[] comparableArray) {

        sort(comparableArray, 0, comparableArray.length - 1);
    }

    private void sort(Item[] comparableArray, int low, int high) {
        if (high <= low + M) {
//            insertionSort.sort(comparableArray);
//      对于小数组，快速排序比插入排序慢，因为递归，
//            快速排序的sort方法在小数组中也会调用自己
//            因此，在排序小数组时应该切换到插入排序
            for (int i = low; i < high; i++) {
                for (int j = i; j > 0 && super.less(comparableArray[j], comparableArray[j - 1]); j--) {
                    super.exchange(comparableArray, j, j - 1);
                }
            }

            return;
        }
        int j = partition(comparableArray, low, high);
        sort(comparableArray, low, j - 1);
        sort(comparableArray, j + 1, high);
    }


    private int partition(Item[] comparableArray, int low, int high) {
        int i = low;
        int j = high + 1;
        int mid = i;
        while (true) {
//            之所以先++的原因是：mid取的就是low本值，所以low不用在左侧参与比较
            while (super.less(comparableArray[++i], comparableArray[mid])) {
                if (i == high) {
                    break;
                }
            }
//            先--的原因是，j = high+1，所以这里直接先减掉
            while (super.less(comparableArray[mid], comparableArray[--j])) {
                if (j == low) {
                    break;
                }
            }
            if (i >= j) {
                break;
            }
            super.exchange(comparableArray, i, j);
        }
        super.exchange(comparableArray, low, j);
        return j;

    }
}
